package leetcode101.ch5;

//LC 347

import java.util.*;

/**
 * 桶排序
 * 1、用一个map统计频次
 * 2、遍历map，用一个list的数组保存数据，以频次为数组下标
 * 3、反向遍历数组，取出前K个不为空的
 */
public class TopKFreqElement {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        //TODO 用下标表示频次，需要跳过下标0， 所以数组长度要+1
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : map.keySet()) {
            List<Integer> bucket = buckets[map.get(key)];
            if (bucket == null) {
                bucket = new ArrayList<>();
            }
            bucket.add(key);
            buckets[map.get(key)] = bucket;
        }
        List<Integer> tmp = new ArrayList<>();
        for (int i = buckets.length - 1; i >=0  ; i--) {
            if (tmp.size() >= k) {
                break;
            }
            List<Integer> bucket = buckets[i];
            if (bucket != null) {
                tmp.addAll(bucket);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,2,2,3};
        int k = 2;
        int[] res = new TopKFreqElement().topKFrequent(nums, k);
        System.out.println(Arrays.toString(res));
    }
}
